package com.gxc.tree;

import java.util.*;

/**
 * 572. 另一棵树的子树

 给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。
 如果存在，返回 true ；否则，返回 false 。

 二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树
 */
public class IsSubtree {

    public static void main(String[] args) {

    }

    public static boolean handle(TreeNode root, TreeNode subRoot) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            TreeNode poll = queue.poll();
            if (poll.val == subRoot.val) {
                if (handle2(poll, subRoot)) {
                    return true;
                }
            }
            if (poll.left != null) {
                queue.add(poll.left);
            }
            if (poll.right != null) {
                queue.add(poll.right);
            }
        }
        return false;
    }

    private static boolean handle2(TreeNode root, TreeNode subRoot) {
        Queue<TreeNode> queue1 = new LinkedList<>();
        queue1.add(root);
        Queue<TreeNode> queue2 = new LinkedList<>();
        queue2.add(subRoot);

        while (!queue1.isEmpty() && !queue2.isEmpty()) {
            TreeNode poll1 = queue1.poll();
            TreeNode poll2 = queue2.poll();

            if (poll1.val != poll2.val) return false;
            if (poll1.left != null && poll2.left == null) return false;
            if (poll1.right != null && poll2.right == null) return false;
            if (poll2.left != null && poll1.left == null) return false;
            if (poll2.right != null && poll1.right == null) return false;

            if (poll1.left != null) {
                queue1.add(poll1.left);
            }
            if (poll1.right != null) {
                queue1.add(poll1.right);
            }

            if (poll2.left != null) {
                queue2.add(poll2.left);
            }
            if (poll2.right != null) {
                queue2.add(poll2.right);
            }
        }
        if (queue1.isEmpty() && queue2.isEmpty()) return true;
        else return false;
    }

    /**
     * 深度优先搜索暴力匹配
     */
    class Solution {
        public boolean isSubtree(TreeNode s, TreeNode t) {
            return dfs(s, t);
        }

        public boolean dfs(TreeNode s, TreeNode t) {
            if (s == null) {
                return false;
            }
            return check(s, t) || dfs(s.left, t) || dfs(s.right, t);
        }

        public boolean check(TreeNode s, TreeNode t) {
            if (s == null && t == null) {
                return true;
            }
            if (s == null || t == null || s.val != t.val) {
                return false;
            }
            return check(s.left, t.left) && check(s.right, t.right);
        }
    }

    class Solution2 {
        List<Integer> sOrder = new ArrayList<Integer>();
        List<Integer> tOrder = new ArrayList<Integer>();
        int maxElement, lNull, rNull;

        public boolean isSubtree(TreeNode s, TreeNode t) {
            maxElement = Integer.MIN_VALUE;
            getMaxElement(s);
            getMaxElement(t);
            lNull = maxElement + 1;
            rNull = maxElement + 2;

            getDfsOrder(s, sOrder);
            getDfsOrder(t, tOrder);

            return kmp();
        }

        public void getMaxElement(TreeNode t) {
            if (t == null) {
                return;
            }
            maxElement = Math.max(maxElement, t.val);
            getMaxElement(t.left);
            getMaxElement(t.right);
        }

        public void getDfsOrder(TreeNode t, List<Integer> tar) {
            if (t == null) {
                return;
            }
            tar.add(t.val);
            if (t.left != null) {
                getDfsOrder(t.left, tar);
            } else {
                tar.add(lNull);
            }
            if (t.right != null) {
                getDfsOrder(t.right, tar);
            } else {
                tar.add(rNull);
            }
        }

        public boolean kmp() {
            int sLen = sOrder.size(), tLen = tOrder.size();
            int[] fail = new int[tOrder.size()];
            Arrays.fill(fail, -1);
            for (int i = 1, j = -1; i < tLen; ++i) {
                while (j != -1 && !(tOrder.get(i).equals(tOrder.get(j + 1)))) {
                    j = fail[j];
                }
                if (tOrder.get(i).equals(tOrder.get(j + 1))) {
                    ++j;
                }
                fail[i] = j;
            }
            for (int i = 0, j = -1; i < sLen; ++i) {
                while (j != -1 && !(sOrder.get(i).equals(tOrder.get(j + 1)))) {
                    j = fail[j];
                }
                if (sOrder.get(i).equals(tOrder.get(j + 1))) {
                    ++j;
                }
                if (j == tLen - 1) {
                    return true;
                }
            }
            return false;
        }
    }

    class Solution3 {
        static final int MAX_N = 1005;
        static final int MOD = 1000000007;
        boolean[] vis = new boolean[MAX_N];
        int[] p = new int[MAX_N];
        int tot;
        Map<TreeNode, int[]> hS = new HashMap<TreeNode, int[]>();
        Map<TreeNode, int[]> hT = new HashMap<TreeNode, int[]>();

        public boolean isSubtree(TreeNode s, TreeNode t) {
            getPrime();
            dfs(s, hS);
            dfs(t, hT);

            int tHash = hT.get(t)[0];
            for (Map.Entry<TreeNode, int[]> entry : hS.entrySet()) {
                if (entry.getValue()[0] == tHash) {
                    return true;
                }
            }

            return false;
        }

        public void getPrime() {
            vis[0] = vis[1] = true;
            tot = 0;
            for (int i = 2; i < MAX_N; ++i) {
                if (!vis[i]) {
                    p[++tot] = i;
                }
                for (int j = 1; j <= tot && i * p[j] < MAX_N; ++j) {
                    vis[i * p[j]] = true;
                    if (i % p[j] == 0) {
                        break;
                    }
                }
            }
        }

        public void dfs(TreeNode o, Map<TreeNode, int[]> h) {
            h.put(o, new int[]{o.val, 1});
            if (o.left == null && o.right == null) {
                return;
            }
            if (o.left != null) {
                dfs(o.left, h);
                int[] val = h.get(o);
                val[1] += h.get(o.left)[1];
                val[0] = (int) ((val[0] + (31L * h.get(o.left)[0] * p[h.get(o.left)[1]]) % MOD) % MOD);
            }
            if (o.right != null) {
                dfs(o.right, h);
                int[] val = h.get(o);
                val[1] += h.get(o.right)[1];
                val[0] = (int) ((val[0] + (179L * h.get(o.right)[0] * p[h.get(o.right)[1]]) % MOD) % MOD);
            }
        }
    }


    /**
     * 深度优先搜索序列上做串匹配
     */
    public class TreeNode {
          int val;
          TreeNode left;
          TreeNode right;
          TreeNode() {}
          TreeNode(int val) { this.val = val; }
          TreeNode(int val, TreeNode left, TreeNode right) {
              this.val = val;
              this.left = left;
              this.right = right;
          }
     }
}
